package com.zlp.partice;

import org.junit.Test;

import java.util.*;

/**
 * @author: zhulaiping
 * @time: 2022/8/12 9:56
 */
public class Day20220812 {

    public List<List<Integer>> groupThePeople(int[] groupSizes) {
        List<List<Integer>> ret = new ArrayList<>();
        Map<Integer,List<Integer>> map = new HashMap<>();
        for (int i=0;i<groupSizes.length;i++){
            List<Integer> list = map.getOrDefault(groupSizes[i], new ArrayList<>());
            list.add(i);
            if(list.size() == groupSizes[i]){
                ret.add(list);
                list = new ArrayList<>();
            }
            map.put(groupSizes[i],list);
        }
        return ret;
    }

    public int maxScore(String s) {
        int zeroCount=0,oneCount = 0,ret = 0;
        char[] arr = s.toCharArray();
        for (int i=0;i<arr.length;i++){
            if(arr[i] == '1') oneCount++;
        }
        for (int i=0;i<arr.length;i++){
            if(arr[i] == '0') zeroCount++;
            else oneCount--;
            ret = Math.max(ret,zeroCount+oneCount);
        }
        return ret;
    }


    class MyCircularDeque {

        LinkedList<Integer> list;
        int size;

        public MyCircularDeque(int k) {
            list = new LinkedList<>();
            size = k;

        }

        public boolean insertFront(int value) {
            if(isFull()) return false;
            list.add(0,value);
            return true;
        }

        public boolean insertLast(int value) {
            if(isFull()) return false;
            list.add(value);
            return true;
        }

        public boolean deleteFront() {
            if(isEmpty()) return false;
            list.removeFirst();
            return true;
        }

        public boolean deleteLast() {
            if(isEmpty()) return false;
            list.removeLast();
            return true;
        }

        public int getFront() {
            if(isEmpty()) return -1;
            return list.peekFirst();
        }

        public int getRear() {
            if(isEmpty()) return -1;
            return list.peekLast();
        }

        public boolean isEmpty() {
            return list.isEmpty();
        }

        public boolean isFull() {
            return list.size() == size;
        }
    }

    String[] arr;
    int ptr = 1;
    public void OrderedStream(int n) {
        arr = new String[n+1];
    }

    public List<String> insert(int idKey, String value) {
        arr[idKey] = value;
        List<String> ret = new ArrayList<>();
        if(idKey!=ptr) return ret;
        for (int i=ptr;i<arr.length;i++){
            if(arr[i]==null){
                ptr = i;
                break;
            }
            ret.add(arr[i]);
        }

        return ret;
    }

    public int deepestLeavesSum(Day20220701.TreeNode root) {
        Queue<Day20220701.TreeNode>queue = new ArrayDeque<>();
        queue.offer(root);
        int ret = 0;
        while (!queue.isEmpty()){
            int size = queue.size(),cur = 0;
            for (int i=0;i<size;i++){
                 Day20220701.TreeNode node = queue.poll();
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                cur+= node.val;
            }
            ret = cur;
        }
        return ret;
    }

    public int busyStudent(int[] startTime, int[] endTime, int queryTime) {
        int ret = 0;
        for (int i=0;i<startTime.length;i++){
            if(startTime[i]<=queryTime && endTime[i]>=queryTime){
                ret ++;
            }
        }
        return ret;
    }

    @Test
    public void dd(){


        isPrefixOfWord("i am tired","you");
    }

    public int isPrefixOfWord(String sentence, String searchWord) {
        String[] s = sentence.split(" ");
        int ret = -1;
        for (int j=0;j<s.length;j++) {
            boolean isFlag = true;
            for (int i=0;i<Math.min(s[j].length(), searchWord.length());i++){
                if(s[j].charAt(i) != searchWord.charAt(i)){
                    isFlag = false;
                    break;
                }
            }
            if(isFlag){
                return j+1;
            };
        }
        return ret;
    }

    public boolean canBeEqual(int[] target, int[] arr) {
        int[] cnt = new int[1001];
        for (int i=0;i<target.length;i++){
            cnt[target[i]]++;
            cnt[arr[i]]--;
        }
        for (int i=0;i<1001;i++){
            if(cnt[i]!=0) return false;
        }
        return true;
    }


    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int l = 0,r = arr.length-1;
        while (r-l != k-1){
            if(Math.abs(arr[l]-x) <= Math.abs(arr[r]-x)) r--;
            else l++;
        }
        List<Integer> ret = new ArrayList<>();
        for (int i=l;i<=r;i++){
            ret.add(arr[i]);
        }
        return ret;
    }

    public int[] finalPrices(int[] prices) {
        for(int i=0;i<prices.length;i++){
            for (int j=i+1;j<prices.length;j++){
                if(prices[j]<=prices[i]){
                    prices[i] -= prices[j];
                    break;
                }
            }
        }
        return prices;
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
   }
    int max;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return Math.max(0,max-1);
    }

    private int dfs(TreeNode root) {
        if(root==null) return 0;
        int ans = 1,cur = 1,l = dfs(root.left),r = dfs(root.right);
        if(root.left!=null&&root.val == root.left.val){
            cur += l;
            ans += l;
        }
        if(root.right!=null&&root.val == root.right.val){
            cur += r;
            ans = Math.max(ans,r+1);
        }
        max = Math.max(max,cur);
        return ans;
    }

    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs,((o1, o2) -> o1[1]-o2[1]));
        int cur = Integer.MIN_VALUE,ret = 0;
        for (int[] pair:pairs){
            if(pair[0]<=cur) continue;
            ret++;
            cur = pair[1];
        }
        return ret;
    }

    public int numSpecial(int[][] mat) {
        int row = mat.length,column = mat[0].length,ret = 0;
        for (int i=0;i<row;i++){
            for (int j=0;j<column;j++){
                if(mat[i][j] == 1 && isFlag(i,j,row,column,mat)){
                    ret++;
                }
            }
        }
        return ret;
    }

    private boolean isFlag(int curi, int curj, int row, int column, int[][] mat) {
        for (int i=0;i<row;i++){
            if(i == curi) continue;
            if(mat[i][curj] == 1) return false;
        }
        for (int i=0;i<column;i++){
            if(i==curj) continue;
            if(mat[curi][i] == 1) return false;
        }
        return true;
    }

    List<TreeNode> ret;
    Set<String> set = new HashSet<>();
    Set<String> added = new HashSet<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        ret = new ArrayList<>();
        dfs1(root);
        return ret;
    }

    private void dfs1(TreeNode root) {
        if (root == null) return;
        StringBuilder sb = new StringBuilder();
        dfs2(root, sb);
        if (!set.contains(sb.toString())) {
            set.add(sb.toString());
        } else if(!added.contains(sb.toString())){
            added.add(sb.toString());
            System.out.println(sb.toString());
            ret.add(root);
        }
        dfs1(root.left);
        dfs1(root.right);
    }

    private void dfs2(TreeNode root, StringBuilder sb) {
        if (root == null) {
            sb.append(",");
            return;
        }
        sb.append(root.val+",");
        dfs2(root.left, sb);
        dfs2(root.right, sb);
    }


    public int uniqueLetterString(String s) {
        Map<Character, List<Integer>>map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i=0;i<chars.length;i++){
            if(!map.containsKey(chars[i])){
                map.put(chars[i],new ArrayList<>());
                map.get(chars[i]).add(-1);
            }
            map.get(chars[i]).add(i);
        }
        int ret = 0;
        for (List<Integer> list:map.values()){
            list.add(chars.length);
            for (int i=1;i<list.size()-1;i++){
                ret += (list.get(i)-list.get(i-1))*(list.get(i+1)-list.get(i));
            }
        }
        return ret;
    }

    @Test
    public void aa(){
        reorderSpaces("  this   is  a sentence ");
    }

    public String reorderSpaces(String text) {
        int space = 0;
        String[] s = text.split(" ");
        for (char ch:text.toCharArray()){
            if(ch == ' ') space++;
        }
        List<String> list = new ArrayList<>();
        for (int i=0;i<s.length;i++){
            if("".equals(s[i])) continue;
            list.add(s[i]);
        }
        int cnt = list.size()==1?space:space/(list.size()-1);
        int cnt2 = list.size()==1?space:space%(list.size()-1);
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<list.size();i++){
            sb.append(list.get(i));
            if(i == list.size()-1) continue;
            for (int j=0;j<cnt;j++){
                sb.append(' ');
            }
        }
        for (int j=0;j<cnt2;j++){
            sb.append(' ');
        }
        return sb.toString();
    }

    public int[] constructArray(int n, int k) {
        int[] ret = new int[n];
        int val = 1, val2 = n;
        for (int i = 0; i < k; i++) {
            ret[i] = i % 2 == 0 ? val2-- : val++;
        }
        for (int i = k; i < n; i++) {
            ret[i] = k % 2 == 0 ? val++ : val2--;
        }
        return ret;
    }


    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null ) return null;
        if(root.val<low) return trimBST(root.right,low,high);
        if(root.val>high) return trimBST(root.left,low,high);
        if(root.val==low){
            root.left = null;
            root.right = trimBST(root.right,low,high);
        }else if(root.val==high){
            root.right = null;
            root.left = trimBST(root.left,low,high);
        }else {
            root.left = trimBST(root.left,low,high);
            root.right = trimBST(root.right,low,high);
        }
        return root;
    }


    public int specialArray(int[] nums) {
        for (int i=0;i<=nums.length;i++){
            int cnti = 0;
            for (int val:nums){
                if(val>i) cnti++;
            }
            if(cnti == i) return i;
        }
        return -1;
    }

    public int maximumSwap(int num) {
        char[] chars = String.valueOf(num).toCharArray();
        PriorityQueue<Character> queue = new PriorityQueue<>((o1, o2) -> o2-o1);
        for (char ch:chars) queue.add(ch);
        for (int i=0;i<chars.length;i++){
            Character cur = queue.poll();
            if(cur == chars[i]) continue;
            for (int j=chars.length-1;j>i;j--){
                if(chars[j]==cur){
                    char temp = chars[i];
                    chars[i] = chars[j];
                    chars[j] = temp;
                    break;
                }
            }
            break;
        }
        return Integer.parseInt(new String(chars));
    }

    public double trimMean(int[] arr) {
        int subLen = arr.length/20,sum = 0;
        Arrays.sort(arr);
        for (int i=subLen;i<arr.length-subLen;i++){
            sum += arr[i];
        }
        return sum*1.0/(arr.length-2*subLen);
    }

    public int maxLengthBetweenEqualCharacters(String s) {
        int[] map = new int[26];
        int ret = 0;
        char[] chars = s.toCharArray();
        for (int i=0;i<chars.length;i++){
            int index = chars[i] - 'a';
            if(map[index] == 0){
                map[index] = i;
            }else{
                ret = Math.max(ret,i-map[index]);
            }
        }
        return ret;
    }

    public void aaa(){
        System.out.println("aaaaaaa");
        System.out.println("回滚");
    }
}
